충족 가능성 문제

명제 논리식을 만족시키는 변수 집합이 존재하는지 검사하는 결정문제. 예를 들어 a AND not B는 a가 TRUE이고 b가 FALSE이면 참이므로 이 식은 “만족가능(satisfiable)“하다.